package algorithm_demo.leetcode;

import java.util.Stack;

/**
 * 20. 有效的括号
 * <a href="https://leetcode.cn/problems/valid-parentheses/">https://leetcode.cn/problems/valid-parentheses/</a>
 * @author Api
 * @date 2023/4/29 16:51
 */
public class Problem_020_ValidParentheses {
    public static void main(String[] args) {
        String str = "{}[]()";
        boolean valid = isValid(str);
        System.out.println(valid);
    }

    public static boolean isValid(String s) {
        if (s == null || s.length() == 0){
            return true;
        }
        char[] str = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char cha : str) {
            if (cha == '(' || cha == '[' || cha == '{') {
                stack.add(cha);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char last = stack.pop();
                if ((cha == ')' && last != '(') || (cha == ']' && last != '[') || (cha == '}' && last != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
